import javax.print.attribute.standard.PresentationDirection;

public class HashBuck {
    static class Node{
        public int key ;
        public int val ;
        public Node next ;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
     public Node[] array ;
    public  int usedSize ;

    public HashBuck() {
        this.array = new Node[10];
    }

    public void put(int key , int val){
          int index = key % array.length;
          Node cur = array[index] ;
         // 先遍历整体的链表，是否存在key
        while (cur != null){
            if(cur.key == key){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //没有这个key
        //使用头插
        Node node = new Node(key , val);
         node.next = array[index] ;
         array[index] = node ;
         usedSize ++ ;

          //把元素输入进来还有计算负载因子
          //如果负载因子超过某个范围，就需要扩容
        if(loadFactor() >= 0.75){
            resize() ;
        }


    }




    //计算负载因子
    //负载因子 = 元素个数 / 数组长度
 private double loadFactor(){
        return (usedSize * 1.0) / array.length;
 }


    //扩容
private void resize(){
   //扩容 ,将数据扩容两倍
    Node[] tmpArr = new Node[array.length * 2] ;
    //遍历原来的数组，把所有元素重新哈希到新的数组
    for (int i = 0; i < array.length; i++) {
        Node cur = array[i] ;
        while (cur != null){
            //记录cur的下一个
            Node curNext = cur.next ;
            //头插法
            //计算 根据新的大小计算 新的位置
            int newIndex = cur.key % tmpArr.length;
            cur.next = tmpArr[newIndex] ;
            tmpArr[newIndex] = cur ;
            cur = curNext ;
        }
    }
    //把新数组个array
    this.array = tmpArr;

}

//get，通过key获取value
    public  int get(int key){
        //求下标
        int index = key % array.length ;
        Node cur = array[index] ;
        while(cur != null){
            if(cur.key == key){
                return cur.val;
            }
            cur = cur.next;
        }
        return  -1  ;

    }




}
